import java.util.Arrays;
import java.util.HashMap;

public class LC1679 {
    /**
     * 平均时间复杂度：NlogN，最坏时间复杂度：N^2
     */
    public static int maxOperationsSort(int[] nums, int k) {
        Arrays.sort(nums);

        int length = nums.length;
        int left = 0, right = length - 1;
        int operationCount = 0;
        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum == k) {
                operationCount++;
                left++;
                right--;
            }
            else if (sum < k) left++;
            else right--;
        }

        return operationCount;
    }

    /**
     * 统计nums中每个数字x的出现次数。当x≠k-x时，nums中所有的x和k-x可以组成min(count(x),count(k-x))对；
     * 当x=k-x时，可以组成floor(count(x))对。
     * 这个解法实际上跟双指针没什么关系。
     */
    public static int maxOperationsHash(int[] nums, int k) {
        int operationCount = 0;
        HashMap<Integer, Integer> map = new HashMap<>();

        for (int num : nums) {
            int count = map.getOrDefault(num, 0);
            map.put(num, count + 1);
        }

        for (int num : nums) {
            int numCount = map.get(num);
            if (numCount > 0) {
                map.put(num, numCount - 1);

                if (map.containsKey(k - num)) {
                    int complementaryCount = map.get(k - num);
                    if (complementaryCount > 0) {
                        operationCount++;
                        map.put(k - num, complementaryCount - 1);
                    } // 如果k-x的数量小于等于0，则不会造成operationCount增加，因此无需再做处理
                }
            }
        }

        return operationCount;
    }

    public static void quickSort(int[] nums, int start, int end) {
        if (end <= start) return;

        int pivot = nums[start];
        int left = start, right = end - 1;
        int pivotIdx = start;
        while (left < right) {
            while (left < right && nums[right] >= pivot) right--;
            if (left < right) {
                nums[left++] = nums[right];
                pivotIdx = right;
            }
            else break; // 指针重合
            while (left < right && nums[left] <= pivot) left++;
            if (left < right) {
                nums[right--] = nums[left];
                pivotIdx = left;
            }
            else break;
        }

        nums[pivotIdx] = pivot;
        quickSort(nums, start, pivotIdx);
        quickSort(nums, pivotIdx + 1, end);
    }

    public static void quickSort(int[] nums) {
        quickSort(nums, 0, nums.length);
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1, 2, 3, 4};
        System.out.println(maxOperationsSort(nums, 5));
    }
}
